#pragma once
#include <iostream>
#include <string>
using namespace std;

namespace xzq
{
    template <class K, class V>
    struct BSTreeNode
    {
        BSTreeNode<K, V> *_left;
        BSTreeNode<K, V> *_right;
        K _key;
        V _val;
        BSTreeNode(const K &key, const V &val)
            : _left(nullptr), _right(nullptr), _key(key), _val(val)
        {
        }
    };

    template <class K, class V>
    class BSTree
    {
        typedef BSTreeNode<K, V> Node;

    public:
        bool Insert(const K &key, const V &val)
        {
            if (_root == nullptr)
            {
                _root = new Node(key, val);
                return true;
            }
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }
            cur = new Node(key, val);
            if (parent->_key < key)
                parent->_right = cur;
            else
                parent->_left = cur;
            return true;
        }
        Node *Find(const K &key)
        {
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return cur;
                }
            }
            return nullptr;
        }
        bool Erase(const K &key)
        {
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    if (cur->_left == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            if (parent->_right == cur)
                                parent->_right = cur->_right;
                            else
                                parent->_left = cur->_right;
                        }
                        delete cur;
                    }
                    else if (cur->_right == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = _root->_left;
                        }
                        else
                        {
                            if (parent->_right == cur)
                                parent->_right = cur->_left;
                            else
                                parent->_left = cur->_left;
                        }
                        delete cur;
                    }
                    else
                    {
                        Node *rightMinparent = cur;
                        Node *rightMin = cur->_right;
                        while (rightMin->_left)
                        {
                            rightMinparent = rightMin;
                            rightMin = rightMin->_left;
                        }
                        cur->_key = rightMin->_key;
                        if (rightMinparent->_left == rightMin)
                            rightMinparent->_left = rightMin->_right;
                        else
                            rightMinparent->_right = rightMin->_right;
                        delete rightMin;
                    }
                    return true;
                }
            }
            return false;
        }
        void _Inorder(Node *root)
        {
            if (root == nullptr)
                return;
            _Inorder(root->_left);
            cout << root->_key << " : " << root->_val << endl;
            _Inorder(root->_right);
        }
        void Inorder()
        {
            _Inorder(_root);
            cout << endl;
        }

    private:
        Node *_root = nullptr;
    };
    void test()
    {
        // BSTree<string, string> dict;
        // dict.Insert("sort", "排序");
        // dict.Insert("string", "字符串");
        // dict.Insert("tree", "树");
        // dict.Insert("insert", "插入");
        // string str;
        // while (cin >> str)
        // {
        //     BSTreeNode<string, string> *ret = dict.Find(str);
        //     if (ret)
        //     {
        //         cout << ret->_val << endl;
        //     }
        //     else
        //     {
        //         cout << "无此单词" << endl;
        //     }
        // }
        string strArr[] = {"西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "西瓜"};
        BSTree<string, int> countTree;
        for (auto str : strArr)
        {
            BSTreeNode<string, int> *ret = countTree.Find(str);
            if (ret == nullptr)
            {
                countTree.Insert(str, 1);
            }
            else
            {
                ret->_val++;
            }
        }
        countTree.Inorder();
    }
}